This invention relates to the field of computer graphics. More specifically, the invention relates to the representation of polygonal models in compressed form suitable for rendering with low latency.
Although the geometric modeling domain is being expanded for mechanical computer aided design (CAD) and for animation modeling systems to include free form surfaces, polygonal models remain the primary three dimensional (3D) representation used in the manufacturing, architectural, geographic information systems, geoscience, and entertainment industries. In particular polygonal models are effective for hardware assisted rendering, which is important for video-games, virtual reality, fly-through, and electronic mockup applications involving complex Computer Aided Design models.
Furthermore, 3D models are being used as a video compression mechanism for teleconferencing and future video coding standards, e.g., motion picture experts group four (MPEG-4), which is to be used in the next generation of cellular phones and for home entertainment systems (set-top boxes).
A polygonal model may be defined by what is referred to as the model""s geometry. A typical definition includes the position of its vertices which are n-dimensional vectors; what is referred to as the model""s connectivity, i.e., the association between each face and its sustaining vertices; and/or, by what is referred to as the model""s properties. A model""s properties may include its colors, normals, and texture coordinates that do not affect the 3D geometry of the model, but that influence the way it is shaded during rendering.
Methods for efficiently representing single-resolution polygonal models in compressed form are known in the prior art. Such methods are known in the art for easily and efficiently triangulating arbitrary polygonal faces. Many of these methods only consider polygonal models that have been defined by triangular meshes. A triangular mesh is a polygonal model in which all model faces are represented as triangles. Graphs and trees for managing these triangular meshes are generally described by R. E. Tarjan in xe2x80x9cData Structures and Network Algorithms,xe2x80x9d SIAM, 1983, which is incorporated herein by reference.
New compression methods and systems for compressing polygonal models are described in detail in U.S. Pat. No. 5,825,369 entitled xe2x80x9cCompression of Simple Geometric Models Using Spanning Treesxe2x80x9d, to J. Rossignac and G. Taubin, and in U.S. Pat. No. 5,905,507 entitled xe2x80x9cCompression of Geometric Models Using Spanning Treesxe2x80x9d, to J. Rossignac and G. Taubin, both assigned to the assignee of the present invention, incorporated herein by reference in their entirety and collectively referred to hereinafter as Rossignac et al.
Briefly, as described in Rossignac et al., the connectivity of the triangular mesh is preserved, effectively, without loss of information. The vertices of the triangular mesh are organized into a tree referred to as a xe2x80x9cvertex spanning treexe2x80x9d and the triangles of the mesh are organized into a tree referred to as a xe2x80x9ctriangle spanning tree.xe2x80x9d A graph referred to as the graph of the triangular mesh is defined by the vertices and edges of the triangular mesh and includes the vertex spanning tree as a sub-graph. A graph referred to as the dual graph of the triangular mesh is defined by the triangles and edges of the triangular mesh and includes the triangle spanning tree as a sub-graph. What is referred to as the order for the edges of the triangular mesh defines the traversal order of both the vertex spanning tree and the triangle spanning tree. Each shape is represented as a simple polygon formed from triangles, the vertex positions and properties are quantized and what is known as entropy is encoded.
FIG. 1 shows a prior art decoder process 1000, which receives a compressed geometric data stream 1100 as an input and produces an uncompressed geometric data stream 1200 as an output. The percentage of the compressed data stream 1100 that must be received before the decoder 1000 starts producing output is known as decoder latency. In many instances, the decoder 1000 may not be capable of producing an output before receiving the entire compressed data stream 1100 input. If the decoder 1000 must receive the entire bitstream before producing any triangles, it has 100% decoder latency. Ideally, decoder latency is zero and, as the decoder 1000 receives the compressed data input 1100, simultaneously, it produces an uncompressed output 1200.
FIG. 2 is a plot 2000 illustrating decoder latency 2100. The plot 2000 shows the percentage of uncompressed data stream 2300 as a function of the percentage of the compressed data stream 2200. Decoder latency 2100 is the x-axis intercept. Rossignac et al. achieves very good compression efficiency, but at a cost of 100% decoder latency.
Thus, there is a need for a polygon model compression/decompression technique for the transmission of geometry with low latency without added redundancy.
It is therefore a purpose of the present invention to improve geometry compression without added redundancy and with low latency;
It is yet another purpose of the invention to improve compressing, storing, transmitting, decompressing polygonal models;
It is another purpose of the present invention to render polygon models directly from a compressed bitstream without requiring an extra decoding step.
The present invention is a method for modifying and reordering a data bitstream of a geometric model without adding redundancy and with low latency. The bitstream is divided into three parts, two parts much smaller than the third and which are the first part of the datastream. The first two parts are a stitching record defining external edge pairs and a triangle tree record which is a representation of the triangle tree of a simple polygonal model. The third, larger part which includes data records for triangles in the triangle tree. The data records can be received incrementally, and as they are received, triangles are output for display.